﻿#include <iostream>

#define MAX(a,b) (a>b?a:b)

/**
 * 常规方法
 */
static int normalMethod(const int* arr, const size_t arrSize)
{
	int xorSum;
	int xorMax = 0;
	for (int i = 0; i < arrSize; i++)
	{
		xorMax = MAX(arr[i], xorMax);
		xorSum = arr[i];
		for (int j = i - 1; j >= 0; j--)
		{
			xorSum ^= arr[j];
			xorMax = MAX(xorSum, xorMax);
		}
	}

	return xorMax;
}

/**
 * xorSum_from_j_to_i = xorSum_from_0_to_j-1 ^ xorSum_from_0_to_i
 */
static int useItoJ(const int* arr, const size_t arrSize)
{
	int* xorSums = (int*)malloc(arrSize * sizeof(int));
	memset(xorSums, 0, arrSize * sizeof(int));

	int xorSum = 0;
	for (int i = 0; i < arrSize; i++)
	{
		xorSum ^= arr[i];
		xorSums[i] = xorSum;
	}

	int xorMax = 0;
	int cur;
	for (int i = 0; i < arrSize; i++)
	{
		// 以arr[i]结尾的子数组中，xor最大的
		for (int j = 0; j <= i; j++)
		{
			// j->i
			if (j == 0)
			{
				xorMax = MAX(xorMax, xorSums[i]);
			}
			else
			{
				cur = xorSums[i] ^ xorSums[j - 1];
				xorMax = MAX(xorMax, cur);
			}
		}
	}

	free(xorSums);
	return xorMax;
}

class BiggestXorSumTrieTreeNode
{
public:
	/**
     * 本题目的前缀树的每一个节点，只需要0和1两条路径即可
     */
	BiggestXorSumTrieTreeNode(char value);

	/**
	 * 将从0到i的异或和加入到前缀树，生成一条新的路径
	 */
	void add(int num);

	/**
	 * 从前缀树中找到与num进行xor尽可能大的数字
	 */
	int mostXor(int num);

public:
	BiggestXorSumTrieTreeNode* nexts[2];

private:
	char value;
};

BiggestXorSumTrieTreeNode::BiggestXorSumTrieTreeNode(char value)
{
	this->value = value;
	nexts[0] = nullptr;
	nexts[1] = nullptr;
}

void BiggestXorSumTrieTreeNode::add(int num)
{
	BiggestXorSumTrieTreeNode* cur = this;
	for (int n = 31; n >= 0; n--)
	{
		char a = (num >> n) & 1;
		if (!cur->nexts[a])
		{
			cur->nexts[a] = new BiggestXorSumTrieTreeNode(a);
		}

		cur = cur->nexts[a];
	}
}

int BiggestXorSumTrieTreeNode::mostXor(int num)
{
	int res = 0;
	BiggestXorSumTrieTreeNode* cur = this;
	char expect;
	for (int n = 31; n >= 0; n--)
	{
		char a = (num >> n) & 1;
		if (n == 31)
		{
			// 符号位，需要尽可能凑正数
			// 对于符号位而言，cur->nexts[1]只有在arr都是正数的情况下，才会null，arr都是正数，expect也不可能等于1
			expect = a;
		}
		else
		{
			// 高位尽可能凑非a
			expect = !a;
		}

		if (!cur->nexts[expect])
		{
			expect = !expect;
		}

		cur = cur->nexts[expect];
		res = (res << 1) | expect;
	}

	return res ^ num;
}

static void releaseTrieTreeNode(BiggestXorSumTrieTreeNode* node)
{
	if (!node) return;

	releaseTrieTreeNode(node->nexts[0]);
	releaseTrieTreeNode(node->nexts[1]);
	delete(node);
}

static int useTrieTree(const int* arr, const size_t arrSize)
{
	if (!arr || arrSize == 0) return 0;
	if (arrSize == 1) return arr[0];

	BiggestXorSumTrieTreeNode* root = new BiggestXorSumTrieTreeNode(0);
	root->add(0);
	int xorSum = 0;
	int biggest = 0;
	int cur;

	for (int i = 0; i < arrSize; i++)
	{
		biggest = MAX(biggest, arr[i]);

		if (i > 0)
		{
			cur = root->mostXor(xorSum ^ arr[i]);
			biggest = MAX(biggest, cur);
		}
		
		xorSum ^= arr[i];
		root->add(xorSum);
	}

	releaseTrieTreeNode(root);
	return biggest;
}

/**
 * 数组异或和的定义: 把数组中所有的数字异或起来得到的值。
 * 给定一个整型数组arr，其中可能有正、有负、有零，求其中子数组的最大异或和
 * 举例：
 * arr=[3]
 * 数组只有1个数，所以只有一个子数组，就是这个数组本身，最大异或和是3
 * arr=[3,-28,-29,2]
 * 子数组有很多，但是[-28,-29]这个子数组的异或和是7，是所有子数组中最大的
 * 
 * 思路：
 * 有一个基本功技巧：求arr中从j到i的异或和，可以用arr{ 从0到j-1的异或和 }^{ 从0到i的异或和 }.
 * 
 * 利用从0到i的异或和构建前缀树，使用前i项的xor和的二进制位信息构建。
 * arr=[3,1,5,2,4]
 * 
 * i==-1时，异或和不包括任何元素，是0，构建：
 *                             A
 *                         0 /
 *                          B
 *                     0  /
 *                       C
 *                   0  /
 *                     D
 * 
 * i==0时，异或和只包括arr[0], xorSum=3(0b011), 构建:
 *                             A
 *                         0 /
 *                          B
 *                     0  /  \ 1
 *                       C    E
 *                   0  /       \ 1
 *                     D          F
 * 
 * i==1时，异或和=arr[0]^arr[1], xorSum=2(0b010), 构建:
 *                             A
 *                         0 /
 *                          B
 *                     0  /  \ 1
 *                       C    E
 *                   0  /  0 /  \ 1
 *                     D    G     F
 * 
 * 
 * i==2时，异或和=arr[0]^arr[1]^arr[2], xorSum=7(0b111), 构建:
 *                             A
 *                         0 /   \ 1
 *                          B     H
 *                     0  /  \ 1    \  1
 *                       C    E      I
 *                   0  /  0 /  \ 1    \ 1
 *                     D    G     F     J
 * 
 * i==3时，异或和=arr[0]^arr[1]^arr[2]^arr[3], xorSum=5(0b101), 构建:
 *                               A
 *                         0 /      \ 1
 *                          B        H
 *                     0  /  \ 1   0/  \  1
 *                       C    E    K    I
 *                   0  /  0 /  \ 1  \ 1  \ 1
 *                     D    G     F   L    J
 * 
 * 则对于arr[4]来说，利用这个前缀树，可以轻松找到以arr[4]结尾，从哪一项到arr[4]的子数组的xor和最大。
 * arr[0]~arr[4]的异或和xorSum是1(0b001)，这时，利用贪心算法，从最高位开始，看能否找到一条路径，使得最高位与xorSum异或出来是1, 期望找到1的路径，即A-H.
 * 然后看次高位，期望次高位与xorSum异或得1，则选A-H-I.
 * 接下来只有一条路径可以走了，故最终路径是A-H-I-J, 以arr[4]结尾的子数组最大异或和是6(0b110).
 * 
 * 同理，用这个思路，将分别以arr[3]、arr[2]、arr[1]、arr[0]结尾的子数组最大异或和求出，然后取最大值即可.
 * 
 * 如果数字中存在负数，则在找路径时，最高位符号位要尽可能凑0.
 * 
 */

int main_biggestXorSum()
{
	int arr[] = {13,-15,0};
	auto arrSize = sizeof(arr) / sizeof(int);
	printf("%d %d\n", normalMethod(arr, arrSize), useTrieTree(arr, arrSize));

	return 0;
}